package 剑指offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class p53_I在排序数组中查找数字 {
    //哈希表
    public int search1(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int num:nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }

        if (map.containsKey(target)) {
            return map.get(target);
        }
        return 0;
    }

    //使用 Arrays.binarySearch()查找 target对应的下标
    public int search2(int[] nums, int target) {
        int index= Arrays.binarySearch(nums,target);
        if (index<0) {
            return 0;
        }

        int left=index-1;
        int right=index+1;
        int len=1;

        //找左边界
        while (left>=0 && nums[left]==target) {
            len++;
            left--;
        }

        //找有边界
        while (right<=nums.length-1 && nums[right]==target) {
            len++;
            right++;
        }
        return len;
    }

    //因为nums是一个排好序的数组，因此可以使用二分法
    public int search3(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        int mid=0;

        //如果找到 target，那么target的次数就是 i-j-1
        //找右边界的值 i
        while (left<=right) {
            mid=(left+right)/2;
            if (nums[mid] <= target) {
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        int i=left;

        if (right>=0 && nums[right]!=target) return 0;

        left=0;
        right=nums.length-1;
        //找左边界的值 j
        while (left<=right) {
            mid=(left+right)/2;
            if (nums[mid] >= target) {
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        int j=right;

        return i-j-1;
    }
}
